NetNews Offline 2/NetNews Offline Volume 2.iso/news/comp/std/c/700

Internet Message Format | 1996-08-06 | 4.1 KB

Path: mail2news.demon.co.uk!genesis.demon.co.uk
From: Lawrence Kirby <[e-mail]>
Newsgroups: comp.std.c
Subject: Re: Restrictions on qsort compare function?
Date: Fri, 05 Apr 96 17:49:42 GMT
Organization: none
Message-ID: <[e-mail]>
References: <4iokop$[e-mail]> <4iqjar$[e-mail]> <4jgltp$[e-mail]> <[e-mail]> <4k28t4$[e-mail]>
Reply-To: [e-mail]
X-NNTP-Posting-Host: genesis.demon.co.uk
X-Newsreader: Demon Internet Simple News v1.27
X-Mail2News-Path: genesis.demon.co.uk

In article <4k28t4$[e-mail]>
           [e-mail] "Peter Curran" writes:

>On Thu, 04 Apr 96 18:57:54 GMT in article <[e-mail]>
>    Lawrence Kirby <[e-mail]> (Lawrence Kirby) wrote:
>
>>In article <4jgltp$[e-mail]>
>>           [e-mail] "James Bonfield" writes:
>
>>>I now agree that non antisymmetric or nontransitive sort comparison functions
>>>are indeed invalid. I can see how this can be construed from the ansi
>>>standard, but can also see how it's possible to construe otherwise.
>
>>I don't. 7.10.5.2:
>
>>"The contents of the array are sorted into ascending
>> order according to a comparison function pointed to by compar".
>
>>If the comparison function produces inconsistent results then it is at odds
>>with that sentence. At best that sentence has no well-defined meaning and
>>the 'sort' operation as a whole has undefined behaviour.
>
><snip>
>
>From the standard:
>>"The function shall return an integer less than, equal to, or greater than
>> zero if the first argument is considered to be respectively less than, equal
>> to, or greater than the second."
>
>Again, agreeing that the intent was that the comparison function be consistent,
>this statement does not require it.  (Actually, consistent is not quite the
> word
>I mean here - it must be consistent with a well-specified definition  - that is
>implied by the first quote, above -  but that definition need not lead to a
>comparison function that produces the same result for the same values on
>successive calls, or follows other "sensible" patterns.)

It *must*  lead to a comparison that produces the same result for the same
values on successive calls or else the term 'sort' is not applicable and
qsort() has undefined behaviour.

>There is nothing here that demands that what one "considers to be ... less
>than", etc., remain static over the duration of a call to qsort().  As I
>suggested earlier, one could define a ordering that is time-dependent, or
>changes in some other way between calls to the comparison function.  I see
>nothing here that precludes a comparison function from then implementing such a
>definition.

Such a comparison function is not consistent with sorting.
It is not the job of the C standard to define basic computer science terms.
Sorting has a well defined meaning and your comparison function is
inconsistent with that meaning.

> As long as the comparison function produces results match the
> rules
>that have been established for considering values to be less than, etc., each
>other each time it is called, whether those rules are static or not,, the
>requirements of the standard have been met.

Undefined behaviour occurs where no behaviour is defined (3.16) i.e. you
don't need to violate an explicit requirement in the standard to invoke it.

>This is clearly "language lawyering" of the worst kind.  Anyone who writes such
>a comparison function will almost certainly get a well-earned mess.  However, I
>see nothing in the standard that contradicts this interpretation.  For logical
>correctness, I think the definition of the comparison function needs to be
>tightened, although its hardly of pressing urgency.)

If you can find any definition as to what the behaviour should be with your
comparison function, explain what it is. Otherwise the behaviour is
undefined.

--
-----------------------------------------
Lawrence Kirby | [e-mail]
Wilts, England | [e-mail]
-----------------------------------------